package com.gary;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * @author peng_rui
 * @date 2022/10/3
 */
public class MeiTuan2 {
    public static void main(String[] args) {
        int[] arr = new int[]{11,12,12,12,33,33,13};
        int[] arr2 = new int[]{11,12,19,33,40};
        int i = bSearch(arr2, 99);
        System.out.println("idx : " + i);
//        int num = searchNum(arr);
//        int[] mergeArr = lambdaMergeArr(arr, arr2);
//        int[] ints = numSort(arr);
//        System.out.println(ints);
    }

    /**
     * 查找一个int数组中出现次数大于数组长度1/2的元素
     * @param a
     * @return
     */
    public static int searchNum(int[] a) {
        int size = a.length / 2;
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : a) {
            if (map.get(num) == null) {
                map.put(num, 1);
            } else {
                Integer count = map.get(num);
                count++;
                if (count > size) {
                    return num;
                } else {
                    map.put(num, count);
                }
            }
        }
        return 0;
    }

    public static int[] mergeArr(int[] a1, int[] a2) {
        int[] newArr = new int[a1.length + a2.length];
        for (int i = 0; i < a1.length; i++) {
            newArr[i] = a1[i];
        }
        int idx = 0;
        for (int i = a1.length; i < a2.length + a1.length; i++) {
            newArr[i] = a2[idx++];
        }
        popSort(newArr);
        return newArr;
    }

    public static void popSort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            boolean flag = true;
            for (int j = 0; j < a.length - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    flag = false;
                }
            }
            if (flag) {
                return;
            }
        }
    }

    public  static int bSearch(int[] a, int target) {
        int left = 0;
        int right = a.length - 1;
        while (left <= right) {
            int mid = left - ((left - right) / 2);
            if (a[mid] == target) {
                return mid;
            }
            if (a[mid] < target && left <= right) {
                left = mid + 1;
            }
            if (a[mid] > target && left <= right) {
                right = mid - 1;
            }
        }

        return -1;
    }

    public static int[] lambdaMergeArr(int[] a1, int[] a2) {
        return IntStream.concat(Arrays.stream(a1), Arrays.stream(a2))
                .sorted().toArray();
    }

    public static int[] numSort(int[] a) {
        Map<Integer, Integer> numMap = new HashMap<>();
        List<NumCount> list = new ArrayList<>();
        Arrays.stream(a).forEach(i -> {
            if (numMap.get(i) == null) {
                numMap.put(i, 1);
            } else {
                Integer count = numMap.get(i);
                count++;
                numMap.put(i, count);
            }
        });
        numMap.forEach((num, count) -> {
            NumCount nc = new NumCount(num, count);
            list.add(nc);
        });
        Collections.sort(list, (n1, n2) -> n2.getCount() - n1.getCount());
        int[] sortArr = new int[a.length];
        int idx = 0;
        for (NumCount n : list) {
            for (int i = 0; i < n.getCount(); i++) {
                sortArr[idx++] = n.getNum();
            }
        }
        return sortArr;
    }
}

class NumCount {
    private Integer num;
    private Integer count;

    public NumCount() {
    }

    public NumCount(Integer num, Integer count) {
        this.num = num;
        this.count = count;
    }

    public Integer getNum() {
        return num;
    }

    public void setNum(Integer num) {
        this.num = num;
    }

    public Integer getCount() {
        return count;
    }

    public void setCount(Integer count) {
        this.count = count;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        NumCount numCount = (NumCount) o;
        return Objects.equals(num, numCount.num) && Objects.equals(count, numCount.count);
    }

    @Override
    public int hashCode() {
        return Objects.hash(num, count);
    }
}
